package com.fanshuai.algorithms.dynamic;

public class Egg {

    /**
     * 高楼扔鸡蛋问题
     *
     * 你面前有一栋从 1 到 N 共 N 层的楼，然后给你 K 个鸡蛋（K 至少为 1）。
     * 现在确定这栋楼存在楼层 0 <= F <= N，在这层楼将鸡蛋扔下去，鸡蛋恰好没摔碎（高于 F 的楼层都会碎，低于 F 的楼层都不会碎）。
     * 现在问你，最坏情况下，你至少要扔几次鸡蛋，才能确定这个楼层 F 呢？
     *
     * 最坏情况：搜索区间穷尽时，鸡蛋仍然没碎
     * 至少扔几次：最坏情况下，最少的搜索次数
     *
     * 假如只有一颗鸡蛋，则需要线性搜索，从1楼到N楼扔鸡蛋，搜索次数为N
     * 假如鸡蛋数量不限，通过二分搜索，可以计算最少的搜索次数, 搜索次数为log2N
     * 那么，如果鸡蛋数量有限，K个鸡蛋，如果计算搜索的最少次数呢？
     *
     * 动态规划解法：
     * 状态：当前拥有的鸡蛋数 K 和需要测试的楼层数 N
     * 选择：去选择哪层楼扔鸡蛋。二分查找每次选择到楼层区间的中间去扔鸡蛋，而线性扫描选择一层层向上测试。不同的选择会造成状态的转移。
     *
     * dp table: dp[K][N]表示K 个鸡蛋，面对 N 层楼时的最优结果
     *
     * dp[i][j] = for 1<=level<=j {
     *     min(res,
     *      max( //最坏情况
     *          dp[i-1][level-1], //鸡蛋碎了
     *          dp[i][j-level] //没碎
     *      ) + 1
     *     )
     * }
     *
     * bad case: k=1, dp[k][n] = n //鸡蛋数 K 为 1 时，显然只能线性扫描所有楼层
     *           n=0, dp[k][n] = 0 //当楼层数 N 等于 0 时，显然不需要扔鸡蛋
     * @param n
     * @param k
     * @return
     */
    public static int dropEggs(int k, int n) {
        int[][] dp = new int[k + 1][n + 1];

        for (int i = 0; i <= k; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = 0;
            dp[1][j] = j;
        }

        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                int res = Integer.MAX_VALUE;

                /**
                 * 1<=level<=j，通过线性搜索确定极小值
                 */
                for (int level = 1; level <= j; level++) {
                    int count = Math.max(dp[i - 1][level - 1], dp[i][j - level]) + 1;
                    res = Math.min(res, count);
                }

                dp[i][j] = res;
            }
        }

        return dp[k][n];
    }

    /**
     * 高楼扔鸡蛋问题改进
     * dp[i][j] = for 1<=level<=j {
     *     min(res,
     *      max( //最坏情况
     *          dp[i-1][level-1], //鸡蛋碎了
     *          dp[i][j-level] //没碎
     *      ) + 1
     *     )
     * }
     *
     * dp table取决于2个函数，dp[i-1][level-1]和dp[i][j-level]。
     * 当固定i和j时，两个函数为level的函数，1<=level<=j。
     *
     * 随着level增大，dp[i-1][level-1]单调递增，dp[i][j-level]单调递减，因此dp[i][j]先单调递减，后单调递增，可以用二分搜索求解最小值
     * @param k
     * @param n
     * @return
     */
    public static int dropEggs2(int k, int n) {
        int[][] dp = new int[k + 1][n + 1];

        for (int i = 0; i <= k; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = 0;
            dp[1][j] = j;
        }

        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                int res = Integer.MAX_VALUE;

                /**
                 * 1<=level<=j，通过二分搜索确定极小值
                 */
                int low = 1;
                int high = j;
                while (low <= high) {
                    int midLevel = (low + high) / 2;  //i颗鸡蛋，楼层数为mid，求总数量
                    int broken = dp[i - 1][midLevel - 1] + 1; //碎
                    int notBroken = dp[i][j - midLevel] + 1; //不碎

                    if (broken > notBroken) {
                        high = midLevel - 1;
                        res = Math.min(res, broken);
                    } else {
                        low = midLevel + 1;
                        res = Math.min(res, notBroken);
                    }
                }

                dp[i][j] = res;
            }
        }

        return dp[k][n];
    }

    public static void main(String[] args) {
        System.out.println(dropEggs(2, 100));
        System.out.println(dropEggs2(2, 100));
    }
}
